package mo.offer_version2;

import mo.common.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class L68_2 {

    private Map<Integer, TreeNode> val2node = new HashMap<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        dfs(root);
        Set<Integer> values = new HashSet<>();
        while (p != null) {
            values.add(p.val);
            p = val2node.get(p.val);
        }
        while (q != null) {
            if (values.contains(q.val)) {
                return q;
            }
            q = val2node.get(q.val);
        }
        return null;
    }

    private void dfs(TreeNode node) {
        if (node.left != null) {
            val2node.put(node.left.val, node);
            dfs(node.left);
        }
        if (node.right != null) {
            val2node.put(node.right.val, node);
            dfs(node.right);
        }
    }


}
